package com.lw.leetcode.dp.a;

/**
 * Created with IntelliJ IDEA.
 * 剑指 Offer II 101. 分割等和子串
 * 416. 分割等和子集
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/27 15:03
 */
public class CanPartition {

    public static void main(String[] args) {
        CanPartition test = new CanPartition();
//        int[] arr = {1, 5, 11, 5};
//        int[] arr = {1,2,4,9};
        int[] arr = {14, 9, 8, 4, 3, 2};
        boolean b = test.canPartition(arr);

        System.out.println(b);
    }


    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }
        sum >>= 1;
        int length = nums.length;

        int[] dp1 = new int[sum + 1];
        int[] dp2 = new int[sum + 1];
        int[] dp3;
        dp1[0] = 1;
        if (nums[0] <= sum) {
            dp1[nums[0]] = 1;
        }
        for (int i = 1; i < length; i++) {
            for (int j = 0; j <= sum; j++) {
                if (dp1[j] == 1 || (nums[i] <= j && dp1[j - nums[i]] == 1)) {
                    dp2[j] = 1;
                }
            }
            if (dp2[sum] == 1) {
                return true;
            }
            dp3 = dp2;
            dp2 = dp1;
            dp1 = dp3;
        }
        return false;
    }

    public boolean canPartition2(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum & 1) == 1) {
            return false;
        }
        sum >>= 1;
        int length = nums.length;
        int[][] dp = new int[length][sum + 1];
        dp[0][0] = 1;

        if (nums[0] <= sum) {
            dp[0][nums[0]] = 1;
        }
        for (int i = 1; i < length; i++) {
            for (int j = 0; j <= sum; j++) {
                if (dp[i - 1][j] == 1 || (nums[i] <= j && dp[i - 1][j - nums[i]] == 1)) {
                    dp[i][j] = 1;
                }
            }
            if (dp[i][sum] == 1) {
                return true;
            }
        }
        return false;
    }
}
